package com.yangzhe.algorithm.c016;

import java.util.Deque;
import java.util.LinkedList;

/**
 * https://leetcode.cn/problems/design-circular-deque/
 */
public class CircularDeque {
    /**
     * 用Java的双向链表实现，常数时间不如循环数组
     */
    class MyCircularDeque1 {
        public Deque<Integer> queue = new LinkedList<>();
        private int limit;

        public MyCircularDeque1(int k) {
            limit = k;
        }

        /**
         * 将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
         *
         * @param value
         * @return
         */
        public boolean insertFront(int value) {
            if (!isFull()) {
                return queue.offerFirst(value);
            } else {
                return false;
            }
        }

        /**
         * 将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
         *
         * @param value
         * @return
         */
        public boolean insertLast(int value) {
            if (!isFull()) {
                return queue.offerLast(value);
            } else {
                return false;
            }
        }

        /**
         * 从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
         *
         * @return
         */
        public boolean deleteFront() {
            if (!isEmpty()) {
                queue.pollFirst();
                return true;
            } else {
                return false;
            }
        }

        /**
         * 从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
         *
         * @return
         */
        public boolean deleteLast() {
            if (!isEmpty()) {
                queue.pollLast();
                return true;
            } else {
                return false;
            }
        }

        /**
         * 从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
         *
         * @return
         */
        public int getFront() {
            if (!isEmpty()) {
                return queue.peekFirst();
            } else {
                return -1;
            }
        }

        /**
         * 获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
         *
         * @return
         */
        public int getRear() {
            if (!isEmpty()) {
                return queue.peekLast();
            } else {
                return -1;
            }
        }

        /**
         * 若双端队列为空，则返回 true ，否则返回 false
         *
         * @return
         */
        public boolean isEmpty() {
            return queue.isEmpty();
        }

        /**
         * 若双端队列满了，则返回 true ，否则返回 false
         *
         * @return
         */
        public boolean isFull() {
            return queue.size() == limit;
        }
    }

    /**
     * 用循环数组实现的方式，常数时间比直接用Java的双向链表要好
     */
    class MyCircularDeque2 {
        public int[] deque;

        private int limit, size, l, r;

        public MyCircularDeque2(int k) {
            deque = new int[k];
            limit = k;
            size = 0;
        }

        /**
         * 将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
         *
         * @param value
         * @return
         */
        public boolean insertFront(int value) {
            if (!isFull()) {
                if (isEmpty()) {
                    l = r = 0;
                } else {
                    // 增加头部，l往左移，0往左移到limit - 1位置
                    l = l == 0 ? limit - 1 : l - 1;
                }
                deque[l] = value;
                size++;
                return true;
            } else {
                return false;
            }
        }

        /**
         * 将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
         *
         * @param value
         * @return
         */
        public boolean insertLast(int value) {
            if (!isFull()) {
                if (isEmpty()) {
                    l = r = 0;
                } else {
                    // 增加到尾部，r往右移，limit - 1 向右移动则来到0位置
                    r = r == limit - 1 ? 0 : r + 1;
                }
                deque[r] = value;
                size++;
                return true;
            } else {
                return false;
            }
        }

        /**
         * 从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
         *
         * @return
         */
        public boolean deleteFront() {
            if (!isEmpty()) {
                // 从头部删除，则l向右移动
                l = l == limit - 1 ? 0 : l + 1;
                size--;
                return true;
            } else {
                return false;
            }
        }

        /**
         * 从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
         *
         * @return
         */
        public boolean deleteLast() {
            if (!isEmpty()) {
                // 从尾部删除，则r向左移动
                r = r == 0 ? limit - 1 : r - 1;
                size--;
                return true;
            } else {
                return false;
            }
        }

        /**
         * 从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
         *
         * @return
         */
        public int getFront() {
            if (!isEmpty()) {
                return deque[l];
            } else {
                return -1;
            }
        }

        /**
         * 获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
         *
         * @return
         */
        public int getRear() {
            if (!isEmpty()) {
                return deque[r];
            } else {
                return -1;
            }
        }

        /**
         * 若双端队列为空，则返回 true ，否则返回 false
         *
         * @return
         */
        public boolean isEmpty() {
            return size == 0;
        }

        /**
         * 若双端队列满了，则返回 true ，否则返回 false
         *
         * @return
         */
        public boolean isFull() {
            return size == limit;
        }
    }

}
